<head>
    <meta charset="UTF-8">
<title>算法训练 奇异的虫群</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】<br />
在一个奇怪的星球上驻扎着两个虫群A和B，它们用奇怪的方式繁殖着，在t+1时刻A虫群的数量等于t时刻A虫群和B虫群数量之和，t+1时刻B虫群的数量等于t时刻A虫群的数量。由于星际空间的时间维度很广阔，所以t可能很大。OverMind 想知道在t时刻A虫群的数量对 p = 1,000,000,007.取余数的结果。当t=1时 A种群和B种群的数量均为1。<br />
【输入格式】<br />
测试数据包含一个整数t，代表繁殖的时间。<br />
【输出格式】<br />
输出一行，包含一个整数，表示对p取余数的结果<br />
【样例输入1】<br />
10<br />
【样例输出1】<br />
89</p>
<p>【样例输入2】<br />
65536<br />
【样例输出2】<br />
462302286<br />
【数据规模和约定】<br />
对于50%的数据 t&lt;=10^9</p>
<p>对于70%的数据 t&lt;=10^15</p>
<p>对于100%的数据 t&lt;=10^18</p>